﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OCRTheNewHope
{
    class DecisionNode
    {
        public DecisionTree Owner { get; private set; }
        public DecisionNode Parent { get; private set; }
        public Digit[] Inputs { get; private set; }
       
        public int? Output { get; private set; }
        public double[] HistogramOutput { get; private set; }
        
        public int Level { get; private set; }
        public Feature SplitFeature { get; set; }
        public DecisionNode[] Branches { get; private set; }
        public double EntropyGain;

        public bool IsRoot
        {
            get { return Parent == null; }
        }

        public bool IsLeaf
        {
            get { return Branches == null || Branches.Length == 0; }
        }

        public DecisionNode(DecisionTree owner, DecisionNode parent, Digit[] inputs)
        {
            this.Owner = owner;
            this.Parent = parent;
            this.Inputs = inputs;

            if (IsRoot)
                this.Level = 0;
            else
                this.Level = this.Parent.Level + 1;
        }

        private Feature[] GetFeatureCandidates()
        {
            Feature[] rVal = new Feature[Parameters.UsedFeatureCountAtEveryNode];

            for (int idx = 0; idx < rVal.Length; idx++)
            {
                rVal[idx] = new Feature();
            }

            return rVal;
        }

        public DecisionNode[] Split()
        {
            Feature[] featureCandidates;
            Digit[][] tempPartition;
            Digit[][] bestPartition;
            int bestAttributeIndex;
            double bestGain;

            double entropy = Entropy(this.Inputs);
            
            if (entropy < Parameters.EntropyThreshold || this.Level > Parameters.MaxDepth)
            {
                TerminateNode();
                return null;
            }

            int counter = 0;
            do
            {
                featureCandidates = GetFeatureCandidates();

                tempPartition = new Digit[2][];
                bestPartition = new Digit[2][];
                double entropyGain;

                bestGain = 0;
                bestAttributeIndex = 0;
                for (int i = 0; i < featureCandidates.Length; i++)
                {
                    entropyGain = ComputeGainRatio(this.Inputs, featureCandidates[i], out tempPartition, entropy);

                    if (entropyGain > bestGain)
                    {
                        bestAttributeIndex = i;
                        bestGain = entropyGain;
                        bestPartition[0] = tempPartition[0].ToArray();
                        bestPartition[1] = tempPartition[1].ToArray();

                        tempPartition[0] = null;
                        tempPartition[1] = null;
                    }
                }

                counter++;
            }
            while (!(bestGain > 4 * Parameters.EntropyThreshold) && counter < 4);

            if (bestGain < Parameters.EntropyThreshold)
            {
                TerminateNode();
                return null;
            }

            this.SplitFeature = featureCandidates[bestAttributeIndex];
            this.EntropyGain = bestGain;
            
            this.Branches = new DecisionNode[2];

            this.Branches[0] = new DecisionNode(this.Owner, this, bestPartition[0]);
            this.Branches[1] = new DecisionNode(this.Owner, this, bestPartition[1]);

            this.Inputs = null;

            return this.Branches;
        }

        private void TerminateNode()
        {
            this.Output = MostCommon(this.Inputs);
            this.HistogramOutput = GetHistogram(this.Inputs);
            this.Inputs = null;        
        }

        private int MostCommon(Digit[] digits)
        {
            int[] frequencies = new int[Parameters.HistogramLength];

            for (int i = 0; i < digits.Length; i++)
                frequencies[digits[i].DigitValue]++;

            return frequencies.MaxIndex();
        }

        public double ComputeGainRatio(Digit[] digits, Feature feature, out Digit[][] partitions, double currentEntropy)
        {
            double infoGain = currentEntropy - ComputeInfo(digits, feature, out partitions);

            return infoGain;
        }

        public double ComputeInfo(Digit[] digits, Feature feature, out Digit[][] bestPartitions)
        {
            bool[][,] digitFeatureArray = new bool[digits.Length][,];

            Digit[][] tempPartitions = new Digit[2][];
            bestPartitions = new Digit[2][];
         
            List<Digit> tempPartitions0 = new List<Digit>(digits.Length);
            List<Digit> tempPartitions1 = new List<Digit>(digits.Length);

            for (int i = 0; i < digits.Length; i++)
            {
                digitFeatureArray[i] = digits[i].ComputeFeature(feature); // false is left, true is right
            }

            double bestEntropy = Parameters.MaxEntropy;
            for (int idx0 = 0; idx0 < 2; idx0++)
            {
                for (int idx1 = 0; idx1 < Parameters.NumberOfThresholds; idx1++)
                {
                    tempPartitions0.Clear();
                    tempPartitions1.Clear();

                    for (int d = 0; d < digits.Length; d++)
                    {
                        if (digitFeatureArray[d][idx0, idx1] == false)
                            tempPartitions0.Add(digits[d]);
                        else
                            tempPartitions1.Add(digits[d]);
                    }

                    tempPartitions[0] = tempPartitions0.ToArray();
                    tempPartitions[1] = tempPartitions1.ToArray();

                    // Compute the information gain obtained by using
                    // this current attribute as the next decision node.
                    double entropy = 0;

                    for (int p = 0; p < tempPartitions.Length; p++)
                    {
                        double e = Entropy(tempPartitions[p]);
                        //TARIK: INPUTS OR DIGITS ?? OR DOESNT MATTER??
                        entropy += ((double)tempPartitions[p].Length / this.Inputs.Length) * e; //
                    }
                    //save best entropy i.e. the min entropy so far
                    if (entropy < bestEntropy)
                    {
                        bestEntropy = entropy;
                        feature.Specify(idx0, idx1);
                        bestPartitions[0] = tempPartitions0.ToArray();
                        bestPartitions[1] = tempPartitions1.ToArray();
                    }
                }
            }

            return bestEntropy;
        }

        public static double Entropy(Digit[] digits)
        {
            if (digits.Length == 0)
                return 0;

            int[] frequencies = new int[Parameters.HistogramLength];
            double[] p = new double[Parameters.HistogramLength];

            for (int i = 0; i < digits.Length; i++)
                frequencies[digits[i].DigitValue]++;

            for (int i = 0; i < frequencies.Length; i++)
                p[i] = (double)frequencies[i] / digits.Length;

            double sum = 0;
            for (int i = 0; i < p.Length; i++)
                if (p[i] != 0) sum += p[i] * Math.Log(p[i], 2);

            return -1 * sum;
        }

        public static double SplitInformation(Digit[][] partitions, int numTotalRecords)
        {
            double info = 0;

            for (int i = 0; i < partitions.Length; i++)
            {
                double p = (double)partitions[i].Length / numTotalRecords;
                if (p != 0)
                    info -= p * Math.Log(p, 2);
            }

            return info;
        }

        public DecisionNode PassToChild(Digit p)
        {
            bool temp = p.ComputeTestFeature(this.SplitFeature);

            if (temp == false)
                return this.Branches[0];
            return this.Branches[1];
        }

        public double[] GetHistogram(Digit[] inputs)
        {
            double[] rVal = new double[Parameters.HistogramLength];

            for (int i = 0; i < inputs.Length; i++)
            {
                rVal[inputs[i].DigitValue]++;
            }

            for (int i = 0; i < rVal.Length; i++)
            {
                rVal[i] = rVal[i] / inputs.Length;
            }

            return rVal;
        }
    }
}
